<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3836：[Poi2014]Tourism</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2014]Tourism</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2014]Tourism</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Poi2014]Tourism                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>King Byteasar believes that Byteotia, a land full of beautiful sights, should attract lots of tourists, who should spend lots of money, which should eventually find their way to the royal treasury. But reality does not live up to his dream. So the king instructed his councilor to look into this issue. The councilor found out that foreigners keep away from Byteotia due to its sparse road network.</div>
<div>Let us remark that there are &nbsp; towns in Byteotia, connected by &nbsp; two way roads, each road linking two different towns. The roads may lead through picturesque overflies and somewhat less picturesque tunnels. There is no guarantee that every town can be reached from every other town.</div>
<div>The councilor observed that the current road network does not allow for a long journey. Namely, wherever one starts the journey, it is impossible to visit more than 10 towns without passing through some town twice.</div>
<div>Due to limited funds in the treasury, no new roads will be constructed at the time. Instead, Byteasar has decided to build a network of tourist information points (TIPs), staffed by officers who are to advertise the short trips that are available. For each town, there should be a TIP either in this town or one of the towns directly linked by a road. Moreover, the cost of building the TIP is known for each town. Help the king by finding the cheapest way of building TIPs that will satisfy aforementioned condition.</div>
<div><span style="white-space: pre-wrap;">给定一个n个点，m条边的无向图，其中你在第i个点建立旅游站点的费用为C[i]。在这张图中，任意两点间不存在节点数超过10的简单路径。</span></div>
<div>
<pre style="white-space: pre-wrap;">
请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。<br /></pre>
</div>
<p></p></p><hr/><h3>输入格式</h3><p><div>The first line of the standard input contains two integers N,M(2&lt;=N&lt;=20 000,0&lt;=m&lt;=25000), separated by a single space, that specify the number of towns and roads in Byteotia respectively. The towns are numbered from &nbsp; to n. The second line of input contains n integers C1,C2&hellip;Cn(0&lt;=Ci&lt;=10000), separated by single spaces; the number Ci specifies the cost of building a TIP in the town no. i.</div>
<div>Then, a description of the Byteotian road network follows. The i-th of the following m lines contains two integers Ai，Bi(1&lt;=Ai&lt;Bi&lt;=N), separated by a single space, that indicate that the towns no. Ai and Bi are linked by a road. There is at most one (direct) road between any pair of towns.</div>
<div><span style="white-space: pre-wrap;">第一行包含两个正整数n,m(1&lt;=n&lt;=20000,0&lt;=m&lt;=25000)，分别表示点数和边数。</span></div>
<div><span style="white-space: pre-wrap;">第二行包含n个整数，其中第i个数为C[i](0&lt;=C[i]&lt;=10000)，表示在第i个点建立旅游站点的费用。</span></div>
<div><span style="white-space: pre-wrap;">接下来m行，每行两个正整数u,v(1&lt;=u,v&lt;=n)，表示u与v之间连了一条边，保证没有重边</span></div>
<p></p></p><hr/><h3>输出格式</h3><p><div>Your program should print out one integer to the standard output: the total cost of building all the TIPs.</div>
<div>
<pre style="white-space: pre-wrap;">
输出一行一个整数，即最小的总费用。		</pre>
</div>
<p></p></p><hr/><h3>样例输入</h3><pre>6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6</pre><hr/><h3>样例输出</h3><pre>7
</pre><hr/><h3>提示</h3><p><p>Explanation: To attain the minimum, the TIPs should be built in towns no. 1, 5, and 6. (the cost will be &nbsp;).</p>
<pre style="white-space: pre-wrap;">
分别在1，5，6号站点建立旅游站点。
</pre>
<div></div>
<div></div>
<p></p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3836" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3836" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>